﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * All square roots are periodic when written as continued fractions and can be written in the form:
√N = a0 + 	
1
  	a1 + 	
1
  	  	a2 + 	
1
  	  	  	a3 + ...

For example, let us consider √23:
√23 = 4 + √23 — 4 = 4 +  	
1
	 = 4 +  	
1
  	
1
√23—4
	  	1 +  	
√23 – 3
7

If we continue we would get the following expansion:
√23 = 4 + 	
1
  	1 + 	
1
  	  	3 + 	
1
  	  	  	1 + 	
1
  	  	  	  	8 + ...

The process can be summarised as follows:
a0 = 4, 	  	
1
√23—4
	 =  	
√23+4
7
	 = 1 +  	
√23—3
7
a1 = 1, 	  	
7
√23—3
	 =  	
7(√23+3)
14
	 = 3 +  	
√23—3
2
a2 = 3, 	  	
2
√23—3
	 =  	
2(√23+3)
14
	 = 1 +  	
√23—4
7
a3 = 1, 	  	
7
√23—4
	 =  	
7(√23+4)
7
	 = 8 +  	√23—4
a4 = 8, 	  	
1
√23—4
	 =  	
√23+4
7
	 = 1 +  	
√23—3
7
a5 = 1, 	  	
7
√23—3
	 =  	
7(√23+3)
14
	 = 3 +  	
√23—3
2
a6 = 3, 	  	
2
√23—3
	 =  	
2(√23+3)
14
	 = 1 +  	
√23—4
7
a7 = 1, 	  	
7
√23—4
	 =  	
7(√23+4)
7
	 = 8 +  	√23—4

It can be seen that the sequence is repeating. For conciseness, we use the notation √23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

√2=[1;(2)], period=1
√3=[1;(1,2)], period=2
√5=[2;(4)], period=1
√6=[2;(2,4)], period=2
√7=[2;(1,1,1,4)], period=4
√8=[2;(1,4)], period=2
√10=[3;(6)], period=1
√11=[3;(3,6)], period=2
√12= [3;(2,6)], period=2
√13=[3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N ≤ 13, have an odd period.

How many continued fractions for N ≤ 10000 have an odd period?

     * */
    class Problem64 : IProblem
    {
        public string Calculate()
        {
            //rjesenje je algoritam za nalazenje continued fractiona za korjene
            //naso ga na netu

            //od korijena, nac cijeli dio i
            //√n = i + 1/x
            //x = 1 / (√n - i)
            //x = (√n + i)/(n - i^2)
            // ako je (n - i^2) == 1
            //  zadnji broj je i + prvi i
            // inace
            //  prosli x = i + 1/x, i opet isti koraci


            //izgled je (√n + nom)/denom = whole + 1/x

            //radi se: x = denom / (√n + nom - whole*denom)
            //zatim: x = (√n + result) / ((n - result^2) / denom)
            //ako je donje jedan, result + prvi whole je zadnji u patternu

            int oddCount = 0;

            for (int n = 2; n <= 10000; n++)
            {

                //int n = 94;
                int nom = 0;
                int denom = 1;
                List<int> CFs = new List<int>(); //Continued Fractions
                double root = Math.Sqrt(n);

                if (root != (int)root)
                {
                    while (true)
                    {
                        int whole = (int)((root + nom) / (double)denom);

                        CFs.Add(whole);

                        int result = nom - whole * denom;
                        nom = -result;
                        denom = (n - result * result) / denom;

                        if (denom == 1)
                        {
                            CFs.Add(CFs[0] + nom);
                            break;
                        }

                    }

                    //foreach (int i in CFs)
                    //    Console.Write(i + " ");
                    //Console.WriteLine();

                    if (CFs.Count % 2 == 0)
                        oddCount++;
                }

            }

            return oddCount.ToString();
        }
    }
}
